﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace WordNet.Core.Graph
{
    // implemented with BFS
    public class DirectedShortestPath: IShortestPath
    {
        private Dictionary<int,bool> _marked;
        private Dictionary<int,int> _edgeTo; 
        private Dictionary<int, int> _distTo;

        public DirectedShortestPath(IDigraph g, int sourceVertex) 
        {
            Init(g);               
            Search(g, sourceVertex);
        }

        public DirectedShortestPath(IDigraph g, IEnumerable<int> sources)
        {
            Init(g);
            Search(g, sources);
        }

        private void Init(IDigraph g)
        {
            _marked = new Dictionary<int, bool>(g.NumberOfVertices);
            _edgeTo = new Dictionary<int, int>(g.NumberOfVertices);
            _distTo = new Dictionary<int, int>(g.NumberOfVertices);
            foreach (var v in g.GetAllVertices())
            {
                _distTo.Add(v, int.MaxValue);
                _marked.Add(v, false);
                _edgeTo.Add(v, 0);
            } 
        }
       
        // BFS
        private void Search(IDigraph g, IEnumerable<int> sources)
        {
            Queue<int> q = new Queue<int>();
            foreach (var item in sources)
            {
                _distTo[item] = 0;
                _marked[item] = true;
                q.Enqueue(item);
            }
            while (q.Count() > 0)
            {
                int temp = q.Dequeue();
                foreach (var w in g.AdjacencyList(temp))
                {
                    if (!_marked[w])
                    {
                        _edgeTo[w] = temp;
                        _distTo[w] = _distTo[temp] + 1;
                        _marked[w] = true;
                        q.Enqueue(w);
                    }
                }
            }
        }
        
         // BFS
        private void Search(IDigraph g, int vertex)
        {
            Queue<int> q = new Queue<int>();
            _distTo[vertex] = 0;
            _marked[vertex] = true;
            q.Enqueue(vertex);
            while (q.Count > 0)
            {
                int currentVertex = q.Dequeue();
                foreach (var item in g.AdjacencyList(currentVertex))
                {
                    if (!_marked[item])
                    {
                        _edgeTo[item] = currentVertex;
                        _marked[item] = true;
                        _distTo[item] = _distTo[currentVertex] + 1;
                        q.Enqueue(item);
                    }
                }
            }
        }
        
        public int DistanceTo(int vertex)
        {
            return _distTo[vertex];
        }

        public bool HasPathTo(int vertex)
        {
           return _marked[vertex];
        }

        public IEnumerable<int> PathTo(int vertex)
        {
            if (!HasPathTo(vertex))
                return null;
            Stack<int> s = new Stack<int>();
            int i;
            for ( i = vertex; _distTo[i] != 0; i = _edgeTo[i])
            {
                s.Push(i);
            }
            s.Push(i);
            return s;
        }
    }
}
